1. Field of the Invention
The present invention relates in general to computer-aided design tools for generating IC layouts and in particular to a method for eliminating routing congestion in an IC layout.
2. Description of Related Art
FIG. 1 illustrates a typical integrated circuit (IC) design process flow. An IC designer usually begins the IC design process by producing a register transfer language (RTL) “netlist” (step 10), a file describing the IC circuit as a set of nets (signal paths) interconnecting terminals of the various circuit devices (“cells”) to be included in the IC. A high level RTL netlist may describe cells in terms of the logic they carry out, using Boolean expressions to define logical relationships between device input and output signals. After employing circuit simulation and verification tools (step 11) to check the logic of the IC described by RTL level netlist 10 and modifying the RTL level design when necessary, the designer uses a synthesis tool (step 12) to convert the RTL level netlist into a “gate level” netlist 14 describing each cell by referring to an entry for that cell in a cell library. The cell library includes an entry for each cell that may be incorporated into an IC design. The entry for each cell describes the layout of each cell and also includes a model of cell behavior that simulation and verification tools employ when checking the logic and timing of the circuit described by gate level netlist (step 14). Cells described by cell library may range from very small devices such as individual transistors and small components such as logic gates formed by several transistors, up to very large components such as computer processors and memories.
After verifying the behavior of the circuit described by the gate level netlist at step 14 and modifying the gate level netlist when necessary, the circuit designer employs computer-aided design tools to convert the gate level netlist into an IC layout including a placement plan describing how each cell is to be formed and positioned within a semiconductor substrate and a routing plan describing how the nets interconnecting the cells are to be routed.
To generate an IC layout, the designer may initially create a floor plan (step 16) reserving particular areas of the semiconductor substrate for one or more large cells. The designer then employs a placement and routing (P&R) tool to generate a global placement plan setting an approximate position of each cell (step 17) in a manner consistent with the floor plan wherein highly interconnected cells tend to cluster near one another. This helps to minimize the space occupied by the nets that are to interconnect the cells. If a satisfactory global placement plan cannot be developed, it may be necessary for the designer to revise the floor plan at step 16 and then try again to develop a suitable global placement plan at step 17.
After generating a global placement plan, the P&R tool then converts the global placement plan generated at step 17 into a detailed placement plan (step 18) specifying the exact position and orientation of each cell in a manner consistent with the global placement plan. If the P&R tool cannot develop a detailed placement plan consistent with the global placement plan, it may return to step 17 to develop a new global placement plan.
After developing a satisfactory detailed placement plan at step 18, the P&R tool develops a detailed routing plan (step 20) describing the paths followed by the nets interconnecting cell terminals. The placement and routing steps 18 and 20 are iterative in that when the P&R tool is unable to develop a routing plan at step 20 providing a suitable route for every net of the design, it returns to step 18 to modify the detailed placement plan and then attempts to develop a suitable routing plan for the altered placement plan at step 20.
After developing placement and routing plans at steps 18 and 20, the designer subjects the layout to various analysis, synthesis and optimization procedures (step 22). For example a clock tree synthesis tool may be employed at step 22 to design one or more clock trees for the IC. A clock tree is a network of buffers for distributing a clock signal to the various registers, flip-flops and other clocked circuit devices. The clock tree design produced at step 22 specifies a position for each buffer forming the clock tree and specifies routing paths interconnecting the buffers that will ensure that each clock signal edge arrives all clocked devices at substantially the same time.
Timing analysis tools may also be employed at step 22 to estimate signal path delays and to develop a buffer insertion plan specifying where buffers of various sizes should be placed in nets interconnecting cells to reduce their signal path delays as necessary to keep the path delays within predetermined limits. Other processes implemented at step 22 may check the design to ensure that it satisfies various design criteria.
Whenever any process carried out at step 22 determines that the layout should be modified in some way, for example to incorporate additional buffers, the P&R tool returns to step 18 to incrementally modify the placement plan and then updates the routing plan at step 20. When the layout satisfies all design criteria, a layout level netlist 26 (an updated version of the gate level netlist which includes behavioral models of the nets generated during the layout process) is subjected to simulation and verification (step 28).
Min-Cut Placement Algorithm
A “min-cut” placement algorithm generally similar to the algorithm illustrated in FIG. 2 is typically employed to generate a global placement plan at step 17 of FIG. 1. FIGS. 3–6 illustrate successive stages of the min-cut placement process carried out by the algorithm of FIG. 2.
Referring to FIGS. 2–6, the min-cut algorithm (step 50) initially divides the substrate area 42 in which cells are to be placed into two partitions 44 and 45 and then randomly allocates cells between the two partitions to create a “seed” placement (step 52). The algorithm then carries out a min-cut optimization process (step 54) in which it moves individual cells from either of partitions 44 and 45 to the other partition in an attempt to minimize the number of nets crossing between the partitions. Since there are a large number of ways to allocate cells between the two partitions, the min-cut optimization process typically will not analyze each option, but it will determine for each cell whether moving the cell across the imaginary line between the two partitions will increase or decrease the number of nets cutting across the partition line. When the move increases the number of nets crossing the partition line, the algorithm leaves the cell in its initial partition. Otherwise when the move decreases the number of nets crossing the partition line, the algorithm reassigns the cell to the other partition.
The algorithm may iteratively repeat the placement and optimization steps 52 and 54 N times, starting with a different seed placements for each iteration so that it produces N different optimized placement alternatives, one for each of the N seed placements. After producing the Nth placement (step 56) the algorithm selects the best placement as the placement for which the minimum number of nets cross partitions lines (step 58).
When partitions 44 and 46 are larger than a predetermined minimum size (step 60), the algorithm partitions the layout again (step 50) so that each partition 44 and 46 becomes a “parent” partition that is itself subdivided into two smaller “child” partitions. As illustrated in FIG. 4, parent partition 44 of FIG. 3 has been divided into two children partitions 47 and 48, and parent partition 46 has been divided into children partitions 49 and 50. The P&R tool then (step 52) generates a seed placement, randomly allocating cells of partition 44 between its children partitions 47 and 48 randomly allocating cells of partition 46 between its children partitions 49 and 50 (step 52). The P&R tool thereafter tries to optimize the cell allocation between children partitions 47 and 48 in a manner that will minimize the total number of nets passing between them, and tries to optimize the allocation between children partitions 49 and 50 in a manner that will minimize the total number of nets passing between them (step 54). The seed placement and optimization steps are repeated N times (step 56) to generate N alternative cell placements for partitions 47–50. The particular placement providing for the smaller number of nets crossing partitions lines is selected at step 58.
As illustrated in FIGS. 5 and 6, the algorithm continues to iteratively repeat the partitioning and optimization process (steps 50–60) with children partitions becoming progressively smaller until they reach a predetermined minimum size at step 60. The placement plan at that point becomes the global placement output of the algorithm. The global placement plan specifies only an approximate position of each cell by indicating the partition to which it is assigned. However when subsequently generating the detailed placement plan at step 18 of FIG. 1, the P&R tool specifies an exact position and orientation for each cell within the partition to which it was assigned in the global placement plan.
By seeking to minimize the number of nets crossing partition lines as it allocates cells between partitions, the min-cut algorithm tends to cluster highly interconnect cells near one another. This helps to reduce the space occupied by the nets interconnecting the cells, and therefore helps to reduce the amount of space needed for the nets when the P&R tool subsequently routes the nets at step 20 of FIG. 1.
Routing Congestion
As the P&R tool develops the detailed routing plan at step 20, it may encounter routing congestion problems arising when there is insufficient space in one or more areas of a layout to accommodate all of the nets that the P&R tool wants to route through those areas. The P&R tool can try to reroute nets around a congested area, but in some cases it may find that there is no way to route a net around a congested area without making the net so long that signal path delays within the net become excessive. In such case, it is necessary for the P&R tool to alter the placement plan and then try to develop a satisfactory routing plan for the altered placement plan.
While a conventional min-cut placement algorithm tries to place cells in a manner that helps to reduce the lengths of nets, thereby reducing the likelihood of routing congestion, it does not directly take routing congestion into account when specifying cell positions. Thus it may be necessary for the P&R tool to iteratively generate several different placement plans and attempt to develop a routing plan for each one, until it produces a placement plan for which it can produce a routing plan that is not subject to routing congestion.
What is needed is a method a P&R tool can employ to modify a placement plan so as to reduce the likelihood that routing congestion problems will arise when the P&R tool subsequently tries to develop a routing plan.